\chapter{Background}
\label{proteinBackground}

Proteins are the executive molecules in the cells. Different proteins have different functions - some proteins are structural proteins responsible for creating diverse structures in the cells, while others may be enzymes that play a vital role in metabolism by catalyzing some biochemical reaction. An organisms entire hereditary information is known as its \index{Genome}genome. The human genome, along with more than 180 other organisms sequenced since 1995, is considered to be fully sequenced \cite{humanGenome, genomeNews}, and the next task at hand is to determine the function of all the proteins that the genes encode, both for human and other organisms.

Comparison of sequences is the most principal operation in protein sequence analysis. When similarities between two proteins are discovered through a comparison of their sequences, a relationship between the two proteins can be suggested. Similar proteins may have similar functions, and a similarity may also propose that the two proteins have evolved from a common ancestor protein. Proteins are mostly compared by trying to align their sequences, either by aligning the entire sequences, or only the most similar parts of the two sequences. If a relationship is discovered between two proteins and one of the proteins is well characterized, the connection with a novel sequence allows all the hard-earned biological data to be transferred to the new protein.

Protein sequences are collected in biological databases. Different types of databases serve different purposes in the research on proteins and their sequences. A new protein sequence can be compared to all the sequences in a protein database in order to uncover potential relationships between the new sequence and the sequences found in the database. Performing a search in a protein database for similarities between two sequences can be a time consuming task, so fast search procedures are necessary to uncover similarities between a sequence and the sequences contained in a protein database.

This chapter introduces important concepts and topics from the fields of biology and bioinformatics related to this thesis, and its contents are based on \cite{eidhammer2, SRM, eidhammer, Steen:2004}, including some of the figures.

\section{Proteins and proteomics}
\index{Protein}
\index{Proteomics}

Proteins consist of one or more \index{Polypeptide}polypeptides (chains of amino acids), with sizes ranging from tens to a few thousand amino acids. There are 20 different amino acids. All amino acids have their own three-letter and one-letter abbreviations used to represent the amino acids in different settings, e.g., Arginine is abbreviated as Arg or R, while Lysine is abbreviated as Lys or K. Cells generally contain thousands of different proteins, each with a specific purpose: some are enzymes that catalyze biochemical reactions, some have structural functions, while others again are important in cell signaling and immune responses. The sequence of a protein's amino acids is distinctive for that protein and is commonly represented by using the amino acids' one-letter abbreviations. A sequence of amino acids' start position is commonly known as the \index{N-terminal}\textit{N-terminal} position, and the end of such a sequence is referred to as the \index{C-terminal}\textit{C-terminal} position.

\begin{quote}
\textit{The overall goal of proteomics is to understand the function of all proteins found in an organism.} \cite{eidhammer}, p. 1.
\end{quote}

There are three basic and important processes that lay the foundation of today's proteomics:
\begin{itemize}
 \item \textit{Protein identification}: With the process of protein identification we can determine which proteins we have in our sample, either by determining the protein's sequence or by measuring sufficiently many of the protein's properties such that it is statistically unlikely that it could be a different protein.
 \item \textit{Protein characterization}: By protein characterization we mean the process of determining a protein's biophysical and/or biochemical properties.
 \item \textit{Protein quantification}: The process where we determine the amount (abundance) of a protein in a sample is called protein quantification. The quantity of a protein in a sample can be measured as either an absolute value or a relative value between two samples.
\end{itemize}

\section{Mass spectrometry}
\index{Mass spectrometry}

The most used approach for performing proteomics is by use of mass spectrometry (MS). This approach can be separated into two paradigms, differing in how the analysis of proteins is performed. Intact proteins are used directly in the analysis in the top-down paradigm, while the bottom-up paradigm first cleaves the proteins into smaller parts known as peptides. Peptides are subsequently used for identification, characterization and quantification. Out of the two, the bottom-up paradigm is most used.

\subsection{Peptides}
\label{sec:peptides}
\index{Peptide}

Peptides are used for analysis in proteomics in place of intact proteins for several reasons. Amongst others, proteins are more difficult to handle than the much shorter peptides, and mass spectrometry instruments typically have a higher sensitivity for peptides than for proteins. For identification purposes, there is need for sequence information - and sequence information is most efficiently found from peptides with a sequence length of up to approximately 20 amino acids, in contrast to entire proteins with sequences of possibly several hundred amino acids. The use of peptides in the analysis of proteins come with a side effect in that only small portions of the entire protein sequence is utilized in the analysis. Smaller portions of a protein sequence are enough to perform protein identification and quantification, but not for fully characterizing a protein.

Proteins are cleaved into peptides by enzymes called proteases. The most commonly used protease is trypsin, since its cleavage is highly specific. Trypsin cleaves after the amino acids Arginine (R) and Lysine (K) if they are not followed by a Proline (P). Cleaving after Arginine or Lysine results in peptides capable of being positively charged, an important physiochemical property when performing analysis by mass spectrometry. With trypsin, proteins are normally cleaved into peptides of suitable length; the desired lengt of a peptide is between 6 and 20 amino acid residues. In some cases a combination of proteases must be used to create peptides of suitable length.

Listing~\ref{protein-sequence} shows an example of how trypsin cleaves a protein sequence. In line 1 the entire sequence is presented, while the same sequence has been cleaved by trypsin in line 2. Note that there is no cleavage after K in the second peptide (because K is followed by a P) and there is no cleavage after the first R in the third peptide (because R is followed by a P).

\begin{lstlisting}[label=protein-sequence, caption=An example protein sequence cleaved by trypsin]
MVPPPPSRGGAAKPGQLGRSLGPLLLLLRPEEPEDGDREICSESKALCGY
MVPPPPSR | GGAAKPGQLGR | SLGPLLLLLRPEEPEDGDR | EICSESK | ALCGY 
\end{lstlisting}

\subsection{Mass spectra and mass spectrometers}

The instruments used in mass spectrometry are known as mass spectrometers. Mass spectrometers are used to determine the \index{Mass-to-charge \textit{(m/z)} ratio}mass-to-charge \textit{(m/z)} ratio of peptides. Peptides normally have 1-3 charges (\textit{z} is usually 1-3). There are three main types of mass spectrometers used in proteomics: Quadrupole mass spectrometers, Time of Flight (TOF) mass spectrometers and Quadropole ion traps. Each of these instruments differ in the manner of which they determine the \textit{m/z} ratio of peptides, but explaining the differences between these instruments is beyond the scope of this thesis. All the different types of mass spectrometers separate peptide ions based on mass. The ions reach a detector at the end of the mass spectrometer at different times according to their mass, and the detector generates \index{Mass spectrum|see{MS spectrum}}mass spectra based on when the ions reach the detector. Signal intensities of the (peptide) ion at each value of the \textit{m/z} scale are recorded in the mass spectrum, known simply as an \index{MS spectrum}MS spectrum. An example of a mass spectrum can be seen in Figure~\ref{fig:mass-spectrum}. The mass-to-charge ratio is placed on the horizontal axis, with a unit of Daltons (Da) per charge, and the vertical axis denotes the intensity of the ions.

Peptides must be ionized in order to appear in a mass spectrum. Ionization of peptides is usually performed by the addition of one or more protons through a process commonly known as electrospray ionization. Tryptic peptides usually become doubly protonated (two protons are added). The mass of tryptic peptides thus becomes \begin{math}(M + 2H)^{2+}\end{math}, where M is the mass of the peptide and \begin{math}H^{+}\end{math} is the mass of a proton.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.23]{figures/mass-spectrum.eps}
\caption{An example mass spectrum. \textit{m/z} ratio on the x-axis and intensities on the y-axis. Each peak corresponds to a peptide.}
\label{fig:mass-spectrum}
\end{figure}

\subsection{Two types of spectra}

After performing the first MS analysis on the peptides, primary structure (sequence) information can be obtained about these peptides through a second MS run. This process is known as MS/MS, or tandem MS, seeing as it combines two stages of MS. In MS/MS a particular peptide, known as the \index{Precursor}\textit{precursor}, from the first MS run is isolated and broken into smaller fragments. A new mass spectrum is generated based on analysis of the fragments created - \index{MS/MS spectrum}the MS/MS spectrum. 

Figure~\ref{fig:msms} shows an example of how an MS/MS spectrum is created. From the MS spectrum a precursor is selected. This precursor is then broken into different fragments and a mass spectrum of the resulting fragments is generated. Each peak in an MS/MS spectrum thus represents a fragment from the precursor selected from the first MS run.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{figures/msms.eps}
\caption{A precursor (a peak in the spectrum) of high abundance in a sample is selected from the MS spectrum. The precursor is fragmented and a new MS analysis is performed, yielding the MS/MS spectrum of the selected precursor's fragments.}
\label{fig:msms}
\end{figure}

\section{Protein quantification}

In general, there are two different types of protein quantification: relative quantification and absolute quantification. In relative quantification one compares the abundance of a protein occuring in each of two or more samples, and determines the ratio of the occurences between samples, while one in absolute quantification determines the absolute abundance (concentration) of a specific protein in a mixture. Absolute quantification thus can be used when analyzing a single sample, and is particularly useful when looking for biomarkers. A \index{Biomarker}biomarker is, e.g., in medicine, any piece of information that can be used to indicate that a specific disease is present, or that an organism has a (high) risk of getting the specific disease. Relative quantification is most used for quantification of proteins, and is, like absolute quantification, useful when identifying biomarkers in samples.

Proteins in samples can be quantified in a number of different ways. Different methods are used depending on \textit{a priori} knowledge about the samples to be quantified. Discovery quantification methods are used to quantify all proteins when the proteins in the considered samples are unknown (no \textit{a priori} knowledge). When the proteins are known (there exists \textit{a priori} knowledge about which proteins are in the samples), targeted quantification methods are more suitable. Often one wishes to find proteins that have different abundances (amounts) in two (or more) samples.

The different methods can also be divided into label-free and label-based methods. Label-based experiments for comparing two samples work principally by labeling one of the samples, which results in that the peptides in the labeled samples are heavier (have a higher mass) than in the unlabeled samples. This results in that the peaks (peptides) of the labeled samples occur in different places than their unlabeled counterparts in the MS-spectrum. An example of such a spectrum can be seen in Figure~\ref{fig:quantification}. In this example, the intensity of the unlabeled peptide is highest.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.6]{figures/quantification.eps}
\caption{MS-spectrum showing the intensities of an unlabeled and a labeled peptide. Peptides are placed on the \textit{m/z} scale according to their mass-to-charge ratio. Assuming that the charge (\textit{z}) is 1, the difference between where the two peptides are placed on the horizontal axis represents the mass of the label.}
\label{fig:quantification}
\end{figure}

\section{Selected Reaction Monitoring}
\label{sec:srm}
\index{Selected reaction monitoring}

The application developed in this thesis is for storing data acquired from a targeted, label-based approach known as Selected Reaction Monitoring (SRM). SRM is the most common method for targeted protein quantification, and is based upon the following: 

\begin{quote}
\textit{If for a protein P there exists a peptide mass m and a fragment mass f that together uniquely determine P in the sample under consideration, then one can target for this pair in the MS-processing. If such a pair is found, the protein is inferred, and the peaks can be used for quantification of that protein.} \cite{SRM}, p. 231.
\end{quote}

The pair (\textit{m, f}), where \textit{m} is a peak (mass of the precursor) in an MS-spectrum and \textit{f} is a peak (fragment mass) in an MS/MS-spectrum, is referred to as a transition, and is considered to be the key element in SRM. An example of such a transition can be seen in Figure~\ref{fig:srm-transition}.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{figures/srm-fragment.eps}
\caption{A transition is a pair of the selected precursor and fragment ion masses. It is important to stress that selecting the same MS-peak and a different MS/MS-peak will result in a different transition.}
\label{fig:srm-transition}
\end{figure}

The methods used for quantification with SRM can also be divided into label-free and label-based methods. The simplest method for use in SRM is label-free quantification, where the relative quantification is based on the signal intensities of specific SRM transitions. As signal intensities will vary from one experiment to the next for a given peptide, this is an inaccurate method and not commonly used in SRM experiments. Label-based quantification increases the cost and complexity of an experiment, but it is also more accurate than label-free quantification and is thus more commonly used in SRM experiments.

\index{Heavy peptides}
There is a possibility that some of the selected peptides in a sample are not labeled properly when utilizing label-based quantification methods. Combined with the fact that signal intensities also vary between different experiments when using label-based quantification methods, the most common procedure for SRM is instead to use internal standards. With this approach, each peptide with a transition has its own standard. These standards are labeled with heavy stable isotopes, and are inserted into the samples. Such standards are usually known as \textit{heavy peptides}. To make sure that the unlabeled and labeled variants of the peptide do not interfere with one another, the labeling has to introduce a sufficiently large mass difference. 

One can calculate the amount of a given peptide relative to its standard from the intensities of the corresponding transitions. The relative abundance of a peptide between two samples can then be calculated from the two standard relative abundances, as illustrated in Figure~\ref{fig:internal-standard}. Here, the same peptide is present in two separate samples and is subsequently compared to a common reference (the standard). Each of the two samples contain the same abundance of the standard. This comparison clearly shows that the abundance of the peptide is much higher in Sample 1 than in Sample 2, an observation which is not obvious when comparing the peaks directly.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.4]{figures/internal-standard.eps}
\caption{Label-based quantification using SRM. The same peptide is found in two separate samples, and are compared to a common reference in order to find which sample contains the highest abundance of the peptide.}
\label{fig:internal-standard}
\end{figure}

\section{Protein databases}

For identification of proteins we use protein databases. As complete genomes are sequenced more and more rapidly, focus is being shifted from the sequencing of genomes to analysis of the proteins which these genomes encode. Vast amounts of data are being generated about these proteins and stored in protein sequence databases. Complete and up-to-date databases containing knowledge derived from the genomes or from common analysis methods such as mass spectrometry make the data available to the scientific community, and are thus vital for the continuous research on the subject \cite{Apweiler:2004}.

Different types of protein databases exist, each serving different types and amounts of data. While universal protein databases cover all species there are also more specialized databases focusing on a particular group of proteins, a protein family, or a specific organism. A universal protein database may be manually curated, meaning that further information can be added to enhance the quality of the different data entries, or it may serve as a sequence repository where little or no additional information is manually added \cite{Apweiler:2004}.

\subsection{Sequence repositories}

Databases classified as sequence repositories are thus the most basic databases containing protein sequence information. Examples of databases which fit the bill of sequence repositories are the GenBank Gene Products Data Bank (GenPept), NCBI's Entrez Protein, and Reference Sequence (RefSeq), all of which are produced by the National Center of Biotechnology Information (NCBI).

According to \citeauthor{Apweiler:2004} \cite{Apweiler:2004}, GenPept and NCBI's Entrez Protein both have a redundant set of database entries, but while GenPept contains very limited annotations, NCBI's Entrez Protein does contain annotations from Swiss-Prot and the Protein Information Resource (PIR) for many of its entries. Redundant protein databases may contain several versions of the same sequence as similar entries are not merged. RefSeq, on the other hand, is based on a slightly more ambitious approach, producing a non-redundant entry set. Although some entries in RefSeq are manually curated, most of the entries are still generated in an automatic fashion, and RefSeq is thus considered to be a sequence repository rather than a manually curated database, which will be discussed below.

\subsection{Manually curated universal databases}

While sequence repositories provide a fast and easy way to acquire sequences, there is a limit to how useful the information contained in these databases are. It quickly becomes clear that when additional information is appended to each sequence entry in the database, the value of the stored information is greatly increased. In manually curated databases the sequence data is enriched by adding additional information reviewed by experienced biologists. The process of manually reviewing the data ensures that these databases contain highly accurate and reliable information.

Two such databases are the Protein Information Resource Protein Sequence Database (PIR-PSD), which is the oldest universal curated protein sequence database (est. 1984); and Swiss-Prot, the leading database of its kind. We will not go into detail about PIR-PSD, but elaborate on Swiss-Prot. 

Swiss-Prot's goal is to provide a database with a very high level of annotation, along with non-redundancy, while at the same time maintaining a high level of integration with other databases \cite{Bairoch:2000}. The rate at which data is generated from the different genome projects presents a problem with the way Swiss-Prot is annotated. A highly rate-limiting step in the process of making the entries of Swiss-Prot available to the public as quickly as possible is the required level of detail of the annotations, a step that calls for careful sequence analysis. According to \citeauthor{Bairoch:2000} \cite{Bairoch:2000} this issue was addressed with the introduction of TrEMBL (Translation of EMBL nucleotide sequence database), which is a database of computer-annotated entries containing all entries from EMBL, except for those entries that already are included in Swiss-Prot.

\subsection{UniProt}
\label{sec:uniProt}

UniProt (Universal Protein resource) is a database of protein sequences of very high quality. It is freely accessible on the web or via different programming APIs (see Chapter~\ref{sec:uniProtJapi}). Its comprehensive collection of protein sequence entries, along with the very high quality of annotations, makes it one of the most significant developments in regards to protein sequence databases \cite{Apweiler:2004}.

PIR-PSD and Swiss-Prot were both incorporated along with TrEMBL into the UniProt Knowledgebase as part of the UniProt project \cite{Butler:2002}. The launch of UniProt in 2003 was the start of an international collaboration between the European Bioinformatics Institue (EBI), the SIB Swiss Institute of Bioinformatics and the Protein Information Resource (PIR), see \cite{uniProtAbout}.

UniProt provides four core databases (see Figure~\ref{fig:uniprot_overview}): the UniProt Knowledgebase (UniProtKB), which is a result of the merging of PIR-PSD and Swiss-Prot, in addition to TrEMBL (as mentioned above); UniProt Archive (UniParc), which is a non-redundant sequence database; UniProt Reference Clusters (UniRef); and UniProt Metagenomic and Environmental Sequences (UniMES), a repository for metagenomic and environmental data \cite{uniProtAbout}. 

\begin{figure}[htb]
\centering
\includegraphics[scale=0.5]{figures/uniprot_overview.eps}
\caption{Overview of the UniProt database \cite{uniProtAbout}. UniProt consists of four core databases: the UniProt Knowledgebase, UniParc, UniRef, and UniMES.}
\label{fig:uniprot_overview}
\end{figure}

\section{Database similarity search}

\begin{quote}
 \textit{An evolutionary perspective is important for getting an understanding of the function of proteins. That means, given two proteins, one often wants to find the evolutionary relationship between them. When only the sequences of the proteins are known, one attempts to reveal the relationship by aligning the sequences. The alignment should therefore show the mutations that have happened in the evolution of the two sequences.} \cite{eidhammer2}, p. 4.
\end{quote}

When comparing sequences one can either perform a global or a local alignment. A global alignment of two sequences can be performed to uncover similarities between two sequences that have maintained a correspondence over their entire length. An alignment is given a score based on a scoring scheme, usually involving a scoring matrix, and the highest scoring alignment is said to be the best representation of the evolutionary relationship between the two sequences. For proteins that are distantly related, global alignment is not capable of uncovering such a relationship. Similar segments might be present in otherwise dissimilar sequences, a relationship that a global alignment might not uncover as the similarities can be lost against a vast number of random matches. Local alignment can be used to find similar subsequences and thus uncover more distant relationships between protein sequences.

\subsubsection{Example of alignments}

Listing~\ref{global-alignments} shows a global alignment of two sequences. The sequence on line 1 is continued on line 4, while the second sequence, starting on line 2, is continued on line 5.

\begin{lstlisting}[language=Java, label=global-alignments, caption=A global alignment of two sequences]
MTP--KARREVEG--PQVGALE----------------------LAGGPG
MNPVIPHKRAMPGADSDLDALNPLQFVQEFEEEDNSISEPLRSALFPGSY

AGGL--------EGPPQKRGIVEQCCAGVCSLYQLENYCN
LGGVLNSLAEVRRRTRQRQGIVERCCKKSCDMKALREYCSVVRN
\end{lstlisting}

A local alignment of the same sequences using the same scoring scheme yields the alignment shown in Listing~\ref{local-alignments}

\begin{lstlisting}[language=Java, label=local-alignments, caption=A local alignment of two sequences]
GIVEQCCAGVCSLYQLENYCN
GIVERCCKKSCDMKALREYCS
\end{lstlisting}

In this example, the local alignment corresponds exactly to a subsection of the global alignment in Listing~\ref{global-alignments}. This is naturally not always the case.\\

\noindent Continually growing protein sequence databases call for efficient search methods over the data sets contained within them. Protein sequence database search programs are used to find sequences in a database that are homologous to a query sequence. The homology is tested by finding the best local alignment between the query and the database sequences, before scoring the local alignment and testing for statistical significance. There exists many database search programs utilized in bioinformatics. Two of the most popular alternatives are FASTA and BLAST (Basic Local Alignment Search Tool). Here, only BLAST will be described.

\subsection{Basic Local Alignment Search Tool}
\index{BLAST}
\label{subsec:blast}

BLAST is one of the most common database search algorithms used in bioinformatics. The BLAST algorithm is a development of the Smith-Waterman algorithm, but where the Smith-Waterman algorithm is time-consuming but accurate, BLAST operates with a more time-optimized model using heuristics. BLAST first uses a fast search method to approximate equality between smaller segments of the two sequences being considered. When such small segment pairs are found it extends the local alignment formed by these segment pairs.

\index{Scoring matrix}Scoring matrices are used to score the local alignments. The most common scoring matrices are the BLOSUM and PAM matrices, which have been developed based on mutations observed in nature. A score matrix assigns a probability score for each position in an alignment. After the local alignments have been given a score S, the e- and p-values of the local alignment's score are calculated. The e-value is defined as \textit{the expected number of segment pairs (alignments) with a score of at least S}, and the p-value is defined as \textit{the probability of finding at least one segment pair with a score greater than or equal to S}. For small values, the e- and p-values are similar.

Based on the e- and p-values of an alignment we can determine whether or not the local alignment is likely to have occured by chance or if it is in fact a significant match. For short sequences the e-value may be too high to provide a statistically significant match.

While dynamic programming algorithms, such as the Smith-Waterman algorithm, are guaranteed to find the best alignment, it is not feasible to search large databases with such algorithms without a super computer, due to time constraints \cite{Altschul:1990}. BLAST has become the de facto standard in regards to database search programs \cite{blastVsSmith}, mainly because it is such a fast method when searching in large databases.

\subsubsection{Search parameters in BLAST search}

When performing BLAST searches it is often suitable to limit the scope of the search in order to exclude unwanted results or include results that otherwise would not appear in the returned list of results. Specifying appropriate BLAST search parameters can be vital in order to obtain results with the desired properties. 

\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{figures/blastform.eps}
\caption{BLAST search tool provided at UniProt's web pages. Advanced search parameters can be adjusted to improve search performance.}
\label{fig:blastform}
\end{figure}

UniProt provides a BLAST search tool on their web pages\footnote{http://www.uniprot.org}, see Figure~\ref{fig:blastform}, with the possibility to customize the search parameters of one's BLAST search. Parameters that can be changed in order to specify the wanted type of results include:

\begin{itemize}
 \item \textit{Database}: With the database parameter it is possible to specify the database against which the search is performed: A search can be performed against the entire UniProtKB; subsets of the UniProtKB, e.g., UniProtKB for sequences related to a specific organism or the Swiss-Prot portion of UniProtKB with manually annotated and reviewed sequences; or for clusters of sequences with either 100\%, 90\%, or 50\% identity.
 \item \textit{Threshold}: One can define a threshold of accepted e-values for hits in a search. Lower e-values mean higher statistical significance of a hit. For short query sequences the threshold may have to be increased in order to uncover weak similarities between the query sequence and any hits found in the selected database.
 \item \textit{Matrix}: It is also possible to specify which scoring matrix to use when scoring the alignments. Matrices from both the BLOSUM and PAM series are available for use. A scoring matrix is selected automatically, dependent on query sequence length, if this option is set to ``Auto.''
 \item \textit{Filtering}: Insignificant matches can be filtered out if the query sequence contains low-complexity regions. Low-complexity regions can, e.g., be the presence of long stretches of the same amino acid in a sequence, and may produce matches in a search that are not biologically related to the query sequence. If activated, this filtering will remove insignificant matches that occur due to these low-complexity regions.
 \item \textit{Gapped}: Specifies whether or not gaps are allowed when sequences are aligned. 
 \item \textit{Hits}: The number of returned alignments can be limited by using this parameter.
\end{itemize}

Properly configuring these search parameters can significantly reduce the chance of insignificant hits being returned for one's query sequence.